#define _CRT_SECURE_NO_WARNINGS	

#include <stdio.h>

int arr[1000001];

void Standard()
{
    arr[1] = 1;
    arr[2] = 2;
    for (int i = 3; i < 1000001; i++)
    {
        arr[i] = (2 * arr[i - 1] + arr[i - 2]) % 32767;
    }
}

int main()
{
    Standard();
    int n;
    scanf("%d", &n);
    int tmp;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &tmp);
        printf("%d\n", arr[tmp]);
    }
}